#include "QtCore"
#include "asserts.h"
#include <QMap>

namespace sk {

template <class T>
Node<T>::Node(const T& value) : pValue(value), pLeft(NULL), pRight(NULL) {
}

template <class T>
T Node<T>::value() {
    return pValue;
}

template <class T>
void Node<T>::setLeft(Node<T>* left) {
    ARG_NOT_NULL(left);
    this->pLeft = left;
}

template <class T>
void Node<T>::setRight(Node<T>* right) {
    ARG_NOT_NULL(right);
    this->pRight = right;
}

template <class T>
int Node<T>::compareTo(const Node<T>& other) const {
    T thisValue = this->pValue;
    T otherValue = other.pValue;
    if (thisValue > otherValue) return 1;
    else if (thisValue == otherValue) return 0;
    else return -1;
}

template <class T>
int Node<T>::compareTo(const T& value) const {
    T thisValue = this->pValue;
    if (thisValue > value) return 1;
    else if (thisValue == value) return 0;
    else return -1;
}



template <class T>
Node<T*>::Node(T* value) : pValue(value), pLeft(NULL), pRight(NULL) {
    ARG_NOT_NULL(value);
}

template <class T>
void Node<T*>::setLeft(Node<T>* left) {
    ARG_NOT_NULL(left);
    this->pLeft = left;
}

template <class T>
void Node<T*>::setRight(Node<T>* right) {
    ARG_NOT_NULL(right);
    this->pRight = right;
}

template <class T>
int Node<T*>::compareTo(const Node<T>& other) const {
    T thisValue = *(this->pValue);
    T otherValue = *(other.pValue);
    if (thisValue > otherValue) return 1;
    else if (thisValue == otherValue) return 0;
    else return -1;
}

template <class T>
int Node<T*>::compareTo(const T* const value) const {
    T thisValue = *(this->pValue);
    if (thisValue > value) return 1;
    else if (thisValue == value) return 0;
    else return -1;
}


//
// Generic template
//

//template <class T>
//BinarySearchTree<T>::BinarySearchTree() : pnRoot(NULL) {}

template <class T>
Node<T>* BinarySearchTree<T>::find(const T& value) const {
    if (pnRoot == NULL) return NULL;
    return _find(pnRoot, value);
}

template <class T>
Node<T>* BinarySearchTree<T>::_find(const Node<T>* const node, const T& value) const {
    ASS(node);

    int r = node->compareTo(value);
    if (r == 0) return node;
    else if (r < 0) return node->pLeft ? _find(node->pLeft, value) : NULL;
    else /*if (r > 0)*/ return node->pRight ? _find(node->pRight, value) : NULL;
}

template <class T>
Node<T>* BinarySearchTree<T>::insert(const T& value) {
    if (pnRoot == NULL) {
        pnRoot = new Node<T>(value);
        return pnRoot;
    } else {
        return _insert(pnRoot, value);
    }
}

template <class T>
Node<T>* BinarySearchTree<T>::_insert(Node<T>* const node, const T& value) {
    int r = node->compareTo(value);
    if (r == 0) {        
        throw std::logic_error("Only distinct elements are supported");
    } else if (r < 0) {
        if (node->pLeft != NULL) return _insert(node->pLeft, value);
        else {
            node->pLeft = new Node<T>(value);
            return node->pLeft;
        }
    }
    else /*if (r > 0)*/ {
        if (node->pRight != NULL) return _insert(node->pRight, value);
        else {
            node->pRight = new Node<T>(value);
            return node->pRight;
        }
    }
}

template <class T>
void BinarySearchTree<T>::_breadthFirst(Node<T>* const node, VisitFunc visit) {
    if (node == NULL) return;

    /*
    QQueue<Node<T>*> Q;
    QQueue<Node<T>*> backQ;

    Q.enqueue(node);

    while(!Q.empty())
    {
        while (!Q.empty()) {
            Node<T>* n = Q.dequeue();

            if (n != NULL) {
                visit(n, -1);
                backQ.enqueue(n->pLeft);
                backQ.enqueue(n->pRight);
            }
        }
        Q.swap(backQ);
    }
    */

    QQueue<Node<T>*> Q1;
    QQueue<Node<T>*> Q2;

    QQueue<Node<T>*>* current = &Q1;
    QQueue<Node<T>*>* another = &Q2;

    current->enqueue(node);

    int level = 0;
    while (!current->empty()) {
        Node<T>* n = current->dequeue();

        if (n != NULL) {
            visit(n, level);
            another->enqueue(n->pLeft);
            another->enqueue(n->pRight);
        }

        if (current->empty()) {
            std::swap(current, another);
            level++;
        }
    }
}

template <class T>
int BinarySearchTree<T>::depth() {
    int result = 0;
    _depth(pnRoot, 0, result);
    return result;
}

template <class T>
int BinarySearchTree<T>::size() {
    int result = 0;
    _size(pnRoot, result);
    return result;
}

template <class T>
void BinarySearchTree<T>::breadthFirst(VisitFunc visit) {
    _breadthFirst(pnRoot, visit);
}

template <class T>
void BinarySearchTree<T>::depthFirstSearch(VisitFunc visit, DepthFirstSearchType type) {
    _depthFirstSearch(pnRoot, visit, type);
}

template <class T>
void BinarySearchTree<T>::_depth(Node<T>* const node, int current, int& result) {
    if (node == NULL) return;
    if (current > result) result = current;
    if (node->pLeft) _depth(node->pLeft, current + 1, result);
    if (node->pRight) _depth(node->pRight, current + 1, result);
}

template <class T>
void BinarySearchTree<T>::_depthFirstSearch(Node<T>* const node, VisitFunc visit, DepthFirstSearchType type) {
    if (node == NULL) return;

    switch (type) {
    case DFST_PREORDER:
        if (node->pLeft) _depthFirstSearch(node->pLeft, visit, type);
        if (node->pRight) _depthFirstSearch(node->pRight, visit, type);
        visit(node, -1);
        break;
    case DFST_INORDER:
        if (node->pLeft) _depthFirstSearch(node->pLeft, visit, type);
        visit(node, -1);
        if (node->pRight) _depthFirstSearch(node->pRight, visit, type);
        break;
    case DFST_POSTORDER:
        visit(node, -1);
        if (node->pLeft) _depthFirstSearch(node->pLeft, visit, type);
        if (node->pRight) _depthFirstSearch(node->pRight, visit, type);
        break;
    }
}

template <class T>
void BinarySearchTree<T>::_size(Node<T>* const node, int& result) {
    if (node == NULL) return;
    result++;
    if (node->pLeft) _size(node->pLeft, result);
    if (node->pRight) _size(node->pRight, result);
}



//
// Specialization for pointers
//

/*
template <class T>
BinarySearchTree<T*>::BinarySearchTree() : pnRoot(NULL) {}

template <class T>
Node<T*>* BinarySearchTree<T*>::find(const T* value) const {
    return NULL;
}

template <class T>
Node<T*>* BinarySearchTree<T*>::_find(const Node<T*>* const node, const T* value) const {
    return NULL;
}

template <class T>
Node<T*>* BinarySearchTree<T*>::insert(const T* value) {
    return NULL;
}

template <class T>
Node<T*>* BinarySearchTree<T*>::_insert(Node<T*>* const node, const T* value) {
    return NULL;
}

template <class T>
void BinarySearchTree<T*>::breadthFirst(Node<T*>* const node, void(*visit)(Node<T*>* const)) {
}
*/

}
